<!DOCTYPE html>
<html lang="en">





<head>
  <meta charset="UTF-8">
  <link rel="apple-touch-icon" sizes="76x76" href="/img/favicon.png">
  <link rel="icon" type="image/png" href="/img/favicon.png">
  <meta name="viewport"
        content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no, shrink-to-fit=no">
  <meta http-equiv="x-ua-compatible" content="ie=edge">
  
  <meta name="theme-color" content="#2f4154">
  <meta name="description" content="My Personal Website For Blog">
  <meta name="author" content="黄宇辉">
  <meta name="keywords" content="learning note,hexo blog">
  <title>详解Queue的实现方式及其应用 - 欢迎参观小灰灰的网站哟 ヾ(◍°∇°◍)ﾉﾞ ~</title>

  <link  rel="stylesheet" href="https://cdn.staticfile.org/twitter-bootstrap/4.4.1/css/bootstrap.min.css" />


  <link  rel="stylesheet" href="https://cdn.staticfile.org/github-markdown-css/4.0.0/github-markdown.min.css" />
  <link  rel="stylesheet" href="/lib/hint/hint.min.css" />

  
    <link  rel="stylesheet" href="https://cdn.staticfile.org/highlight.js/10.0.0/styles/vs2015.min.css" />
  

  


<!-- 主题依赖的图标库，不要自行修改 -->
<link rel="stylesheet" href="//at.alicdn.com/t/font_1749284_yg9cfy8wd6.css">

<link rel="stylesheet" href="//at.alicdn.com/t/font_1736178_pjno9b9zyxs.css">

<link  rel="stylesheet" href="/css/main.css" />

<!-- 自定义样式保持在最底部 -->


  <script  src="/js/utils.js" ></script>
</head>


<body>
  <header style="height: 70vh;">
    <nav id="navbar" class="navbar fixed-top  navbar-expand-lg navbar-dark scrolling-navbar">
  <div class="container">
    <a class="navbar-brand"
       href="/">&nbsp;<strong>ANONYMOUS</strong>&nbsp;</a>

    <button id="navbar-toggler-btn" class="navbar-toggler" type="button" data-toggle="collapse"
            data-target="#navbarSupportedContent"
            aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation">
      <div class="animated-icon"><span></span><span></span><span></span></div>
    </button>

    <!-- Collapsible content -->
    <div class="collapse navbar-collapse" id="navbarSupportedContent">
      <ul class="navbar-nav ml-auto text-center">
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/">
                <i class="iconfont icon-home-fill"></i>
                Home
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/archives/">
                <i class="iconfont icon-archive-fill"></i>
                Archives
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/tags/">
                <i class="iconfont icon-tags-fill"></i>
                Tags
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/about/">
                <i class="iconfont icon-user-fill"></i>
                About
              </a>
            </li>
          
        
        
          <li class="nav-item" id="search-btn">
            <a class="nav-link" data-toggle="modal" data-target="#modalSearch">&nbsp;&nbsp;<i
                class="iconfont icon-search"></i>&nbsp;&nbsp;</a>
          </li>
        
      </ul>
    </div>
  </div>
</nav>

    <div class="view intro-2" id="background" parallax=true
         style="background: url('/img/default.png') no-repeat center center;
           background-size: cover;">
      <div class="full-bg-img">
        <div class="mask flex-center" style="background-color: rgba(0, 0, 0, 0.3)">
          <div class="container text-center white-text fadeInUp">
            <span class="h2" id="subtitle">
              
            </span>

            
              
  <div class="mt-3 post-meta">
    <i class="iconfont icon-date-fill" aria-hidden="true"></i>
    <time datetime="2019-08-31 21:37">
      August 31, 2019 pm
    </time>
  </div>


<div class="mt-1">
  
    
    <span class="post-meta mr-2">
      <i class="iconfont icon-chart"></i>
      1.8k 字
    </span>
  

  
    
    <span class="post-meta mr-2">
      <i class="iconfont icon-clock-fill"></i>
      
      
      31
       分钟
    </span>
  

  
  
</div>

            
          </div>

          
        </div>
      </div>
    </div>
  </header>

  <main>
    
      

<div class="container-fluid">
  <div class="row">
    <div class="d-none d-lg-block col-lg-2"></div>
    <div class="col-lg-8 nopadding-md">
      <div class="container nopadding-md" id="board-ctn">
        <div class="py-5" id="board">
          <div class="post-content mx-auto" id="post">
            
            <article class="markdown-body">
              <h2 id="学习笔记-详解Queue的实现方式及其应用"><a href="#学习笔记-详解Queue的实现方式及其应用" class="headerlink" title="学习笔记 : 详解Queue的实现方式及其应用"></a>学习笔记 : 详解Queue的实现方式及其应用</h2><h3 id="什么是队列"><a href="#什么是队列" class="headerlink" title="什么是队列"></a>什么是队列</h3><p><em>队列是一种只能在一端插入( 队尾 ),在另外一端删除( 堆首 )的有序线性表. 队列中第一个插入的元素也是第一个被删除的元素. 所以,队列是一种先进先出( FIFO,First In First Out )或后进后出( LILO,Last In Last Out )线性表.</em></p>
<h3 id="队列的应用"><a href="#队列的应用" class="headerlink" title="队列的应用"></a>队列的应用</h3><ol>
<li>直接相关的应用</li>
</ol>
<ul>
<li>操作系统根据( 具有相同优先级的 )任务到达的顺序调度任务( 例如,打印队列 )</li>
<li>模拟现实世界中的队列,如售票柜台前的队伍,或者任何需要先来先服务的场景</li>
<li>多道程序设计</li>
<li>异步数据传输( 文件输入输出,管道,套接字 )</li>
</ul>
<ol start="2">
<li>间接相关的应用</li>
</ol>
<ul>
<li>作为算法的辅助数据结构</li>
<li>其他数据结构的组件</li>
</ul>
<h3 id="队列的实现方式"><a href="#队列的实现方式" class="headerlink" title="队列的实现方式"></a>队列的实现方式</h3><p><em>队列抽象数据类型( 与栈类似 )有多种实现方式,下面是常用的方法 :</em></p>
<ul>
<li>基于简单循环数组的实现方法</li>
<li>基于动态循环数据的实现方法</li>
<li>基于链表的实现方法</li>
</ul>
<h4 id="简单循环数组的实现方法"><a href="#简单循环数组的实现方法" class="headerlink" title="简单循环数组的实现方法"></a>简单循环数组的实现方法</h4><div class="hljs"><pre><code class="hljs java"><span class="hljs-keyword">package</span> pers.huangyuhui.queue;


<span class="hljs-keyword">import</span> java.util.Arrays;

<span class="hljs-comment">/**
 * <span class="hljs-doctag">@project</span>: Data structures and algorithms
 * <span class="hljs-doctag">@description</span>: 基于简单循环数组实现队列
 * <span class="hljs-doctag">@author</span>: 黄宇辉
 * <span class="hljs-doctag">@date</span>: 8/31/2019-9:59 PM
 * <span class="hljs-doctag">@version</span>: 1.0
 * <span class="hljs-doctag">@website</span>: https://yubuntu0109.github.io/
 */</span>
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">ArrayQueue</span> </span>&#123;

    <span class="hljs-keyword">private</span> <span class="hljs-keyword">int</span> front;
    <span class="hljs-keyword">private</span> <span class="hljs-keyword">int</span> rear;
    <span class="hljs-keyword">private</span> <span class="hljs-keyword">int</span> capacity;
    <span class="hljs-keyword">private</span> <span class="hljs-keyword">int</span>[] array;

    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">ArrayQueue</span><span class="hljs-params">(<span class="hljs-keyword">int</span> size)</span> </span>&#123;
        <span class="hljs-keyword">this</span>.capacity = size;
        front = rear = -<span class="hljs-number">1</span>;
        array = <span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[size];
    &#125;

    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> ArrayQueue <span class="hljs-title">createQueue</span><span class="hljs-params">(<span class="hljs-keyword">int</span> size)</span> </span>&#123;
        <span class="hljs-keyword">return</span> <span class="hljs-keyword">new</span> ArrayQueue(size);
    &#125;

    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">isEmpty</span><span class="hljs-params">()</span> </span>&#123;
        <span class="hljs-keyword">return</span> (front == -<span class="hljs-number">1</span>);
    &#125;

    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">isFull</span><span class="hljs-params">()</span> </span>&#123;
        <span class="hljs-keyword">return</span> ((rear + <span class="hljs-number">1</span>) % capacity == front);
    &#125;

    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">traverse</span><span class="hljs-params">()</span> </span>&#123;
        System.out.println(Arrays.toString(array));
    &#125;

    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">getQueueSize</span><span class="hljs-params">()</span> </span>&#123;
        <span class="hljs-keyword">if</span> (front == -<span class="hljs-number">1</span>) &#123;
            <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
        &#125;
        <span class="hljs-keyword">int</span> size = (capacity - front + rear + <span class="hljs-number">1</span>) % capacity;
        <span class="hljs-keyword">if</span> (size == <span class="hljs-number">0</span>) &#123;
            <span class="hljs-keyword">return</span> capacity;
        &#125; <span class="hljs-keyword">else</span> &#123;
            <span class="hljs-keyword">return</span> size;
        &#125;
    &#125;

    <span class="hljs-comment">//入队</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">enQueue</span><span class="hljs-params">(<span class="hljs-keyword">int</span> data)</span> </span>&#123;
        <span class="hljs-keyword">if</span> (isFull()) &#123;
            System.err.println(<span class="hljs-string">"error : the queue is overflow"</span>);
        &#125; <span class="hljs-keyword">else</span> &#123;
            rear = (rear + <span class="hljs-number">1</span>) % capacity;
            array[rear] = data;
            <span class="hljs-keyword">if</span> (front == -<span class="hljs-number">1</span>) &#123;
                front = rear;
            &#125;
            System.out.println(<span class="hljs-string">"enter the data into the queue successfully : "</span> + data);
        &#125;
    &#125;

    <span class="hljs-comment">//出队</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">deQueue</span><span class="hljs-params">()</span> </span>&#123;
        <span class="hljs-keyword">int</span> data = <span class="hljs-number">0</span>;
        <span class="hljs-keyword">if</span> (isEmpty()) &#123;
            System.err.println(<span class="hljs-string">"error : the queue is empty"</span>);
        &#125; <span class="hljs-keyword">else</span> &#123;
            data = array[front];
            array[front] = <span class="hljs-number">0</span>;
            <span class="hljs-keyword">if</span> (front == rear) &#123;
                front = rear = -<span class="hljs-number">1</span>;
            &#125; <span class="hljs-keyword">else</span> &#123;
                front = (front + <span class="hljs-number">1</span>) % capacity;
            &#125;
            System.out.println(<span class="hljs-string">"delete the data from the queue successfully : "</span> + data);
        &#125;
        <span class="hljs-keyword">return</span> data;
    &#125;

    <span class="hljs-comment">//test</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> </span>&#123;
        ArrayQueue queue = ArrayQueue.createQueue(<span class="hljs-number">5</span>);
        <span class="hljs-comment">//enter</span>
        queue.enQueue(<span class="hljs-number">1</span>);
        queue.enQueue(<span class="hljs-number">2</span>);
        queue.enQueue(<span class="hljs-number">3</span>);
        queue.enQueue(<span class="hljs-number">4</span>);
        queue.enQueue(<span class="hljs-number">5</span>);
        System.out.println(<span class="hljs-string">"the size of queue : "</span> + queue.getQueueSize());
        System.out.print(<span class="hljs-string">"traverse the queue : "</span>);
        queue.traverse();
        <span class="hljs-comment">//delete</span>
        queue.deQueue();
        queue.deQueue();
        queue.deQueue();
        queue.deQueue();
        queue.deQueue();
        System.out.println(<span class="hljs-string">"the size of queue : "</span> + queue.getQueueSize());
        System.out.print(<span class="hljs-string">"traverse the queue : "</span>);
        queue.traverse();
    &#125;

&#125;</code></pre></div>

<p><em>程序运行结果如下 :</em></p>
<div class="hljs"><pre><code class="hljs java">enter the data into the queue successfully : <span class="hljs-number">1</span>
enter the data into the queue successfully : <span class="hljs-number">2</span>
enter the data into the queue successfully : <span class="hljs-number">3</span>
enter the data into the queue successfully : <span class="hljs-number">4</span>
enter the data into the queue successfully : <span class="hljs-number">5</span>
the size of queue : <span class="hljs-number">5</span>
traverse the queue : [<span class="hljs-number">1</span>, <span class="hljs-number">2</span>, <span class="hljs-number">3</span>, <span class="hljs-number">4</span>, <span class="hljs-number">5</span>]

delete the data from the queue successfully : <span class="hljs-number">1</span>
delete the data from the queue successfully : <span class="hljs-number">2</span>
delete the data from the queue successfully : <span class="hljs-number">3</span>
delete the data from the queue successfully : <span class="hljs-number">4</span>
delete the data from the queue successfully : <span class="hljs-number">5</span>
the size of queue : <span class="hljs-number">0</span>
traverse the queue : [<span class="hljs-number">0</span>, <span class="hljs-number">0</span>, <span class="hljs-number">0</span>, <span class="hljs-number">0</span>, <span class="hljs-number">0</span>]</code></pre></div>


<h4 id="动态循环数据的实现方法"><a href="#动态循环数据的实现方法" class="headerlink" title="动态循环数据的实现方法"></a>动态循环数据的实现方法</h4><div class="hljs"><pre><code class="hljs java"><span class="hljs-keyword">package</span> pers.huangyuhui.queue;

<span class="hljs-keyword">import</span> java.util.Arrays;

<span class="hljs-comment">/**
 * <span class="hljs-doctag">@project</span>: Data structures and algorithms
 * <span class="hljs-doctag">@description</span>: 基于动态循环数组实现队列
 * <span class="hljs-doctag">@author</span>: 黄宇辉
 * <span class="hljs-doctag">@date</span>: 9/1/2019-8:59 AM
 * <span class="hljs-doctag">@version</span>: 1.0
 * <span class="hljs-doctag">@website</span>: https://yubuntu0109.github.io/
 */</span>
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">DynArrayQueue</span> </span>&#123;

    <span class="hljs-keyword">private</span> <span class="hljs-keyword">int</span> front;
    <span class="hljs-keyword">private</span> <span class="hljs-keyword">int</span> rear;
    <span class="hljs-keyword">private</span> <span class="hljs-keyword">int</span> capacity;
    <span class="hljs-keyword">private</span> <span class="hljs-keyword">int</span>[] array;

    <span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-title">DynArrayQueue</span><span class="hljs-params">()</span> </span>&#123;
        capacity = <span class="hljs-number">1</span>;
        front = rear = -<span class="hljs-number">1</span>;
        array = <span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[<span class="hljs-number">1</span>];
    &#125;

    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> DynArrayQueue <span class="hljs-title">createDynArrayQueue</span><span class="hljs-params">()</span> </span>&#123;
        <span class="hljs-keyword">return</span> <span class="hljs-keyword">new</span> DynArrayQueue();
    &#125;

    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">isEmpty</span><span class="hljs-params">()</span> </span>&#123;
        <span class="hljs-keyword">return</span> (front == -<span class="hljs-number">1</span>);
    &#125;

    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">isFull</span><span class="hljs-params">()</span> </span>&#123;
        <span class="hljs-keyword">return</span> ((rear + <span class="hljs-number">1</span>) % capacity == front);
    &#125;

    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">traverse</span><span class="hljs-params">()</span> </span>&#123;
        System.out.println(Arrays.toString(array));
    &#125;

    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">getQueueSize</span><span class="hljs-params">()</span> </span>&#123;
        <span class="hljs-keyword">if</span> (front == -<span class="hljs-number">1</span>) &#123;
            <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>;
        &#125;
        <span class="hljs-keyword">int</span> size = (capacity - front + rear + <span class="hljs-number">1</span>) % capacity;
        <span class="hljs-keyword">if</span> (size == <span class="hljs-number">0</span>) &#123;
            <span class="hljs-keyword">return</span> capacity;
        &#125; <span class="hljs-keyword">else</span> &#123;
            <span class="hljs-keyword">return</span> size;
        &#125;
    &#125;


    <span class="hljs-comment">//扩容</span>
    <span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">resizeQueue</span><span class="hljs-params">()</span> </span>&#123;
        <span class="hljs-keyword">int</span> initCapacity = capacity;
        capacity *= <span class="hljs-number">2</span>;
        <span class="hljs-keyword">int</span>[] oldArray = array;
        array = <span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[<span class="hljs-keyword">this</span>.capacity];
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; oldArray.length; i++) &#123;
            array[i] = oldArray[i];
        &#125;
        <span class="hljs-comment">//important</span>
        <span class="hljs-keyword">if</span> (rear &lt; front) &#123;
            <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; front; i++) &#123;
                array[i + initCapacity] = <span class="hljs-keyword">this</span>.array[i];
                array[i] = <span class="hljs-number">0</span>;
            &#125;
            rear += initCapacity;
        &#125;

    &#125;

    <span class="hljs-comment">//入队</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">enQueue</span><span class="hljs-params">(<span class="hljs-keyword">int</span> data)</span> </span>&#123;
        <span class="hljs-keyword">if</span> (isFull()) &#123;
            resizeQueue();
        &#125;
        rear = (rear + <span class="hljs-number">1</span>) % capacity;
        array[rear] = data;
        <span class="hljs-keyword">if</span> (front == -<span class="hljs-number">1</span>) &#123;
            front = rear;
        &#125;
        System.out.println(<span class="hljs-string">"enter a data into the queue successfully : "</span> + data);
    &#125;

    <span class="hljs-comment">//出队</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">deQueue</span><span class="hljs-params">()</span> </span>&#123;
        <span class="hljs-keyword">int</span> data = -<span class="hljs-number">1</span>;
        <span class="hljs-keyword">if</span> (isEmpty()) &#123;
            System.err.println(<span class="hljs-string">"error : the queue is empty"</span>);
        &#125; <span class="hljs-keyword">else</span> &#123;
            data = array[front];
            array[front] = <span class="hljs-number">0</span>; <span class="hljs-comment">//delete the data</span>
            <span class="hljs-keyword">if</span> (front == rear) &#123;
                front = rear = -<span class="hljs-number">1</span>;

            &#125; <span class="hljs-keyword">else</span> &#123;
                front = (front + <span class="hljs-number">1</span>) % capacity;
            &#125;
            System.out.println(<span class="hljs-string">"delete a data from the queue successfully : "</span> + data);
        &#125;
        <span class="hljs-keyword">return</span> data;
    &#125;


    <span class="hljs-comment">//test</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> </span>&#123;
        DynArrayQueue dynArrayQueue = DynArrayQueue.createDynArrayQueue();
        <span class="hljs-comment">//enter</span>
        dynArrayQueue.enQueue(<span class="hljs-number">1</span>);
        dynArrayQueue.enQueue(<span class="hljs-number">2</span>);
        dynArrayQueue.enQueue(<span class="hljs-number">3</span>);
        dynArrayQueue.enQueue(<span class="hljs-number">4</span>);
        dynArrayQueue.enQueue(<span class="hljs-number">5</span>);
        System.out.println(<span class="hljs-string">"the size of queue : "</span> + dynArrayQueue.getQueueSize());
        System.out.print(<span class="hljs-string">"traverse the queue : "</span>);
        dynArrayQueue.traverse();
        <span class="hljs-comment">//delete</span>
        dynArrayQueue.deQueue();
        dynArrayQueue.deQueue();
        dynArrayQueue.deQueue();
        dynArrayQueue.deQueue();
        dynArrayQueue.deQueue();
        System.out.println(<span class="hljs-string">"the size of queue : "</span> + dynArrayQueue.getQueueSize());
        System.out.print(<span class="hljs-string">"traverse the queue : "</span>);
        dynArrayQueue.traverse();


    &#125;

&#125;</code></pre></div>

<p><em>程序运行结果如下所示 :</em></p>
<div class="hljs"><pre><code class="hljs java">enter a data into the queue successfully : <span class="hljs-number">1</span>
enter a data into the queue successfully : <span class="hljs-number">2</span>
enter a data into the queue successfully : <span class="hljs-number">3</span>
enter a data into the queue successfully : <span class="hljs-number">4</span>
enter a data into the queue successfully : <span class="hljs-number">5</span>
the size of queue : <span class="hljs-number">5</span>
traverse the queue : [<span class="hljs-number">1</span>, <span class="hljs-number">2</span>, <span class="hljs-number">3</span>, <span class="hljs-number">4</span>, <span class="hljs-number">5</span>, <span class="hljs-number">0</span>, <span class="hljs-number">0</span>, <span class="hljs-number">0</span>]

delete a data from the queue successfully : <span class="hljs-number">1</span>
delete a data from the queue successfully : <span class="hljs-number">2</span>
delete a data from the queue successfully : <span class="hljs-number">3</span>
delete a data from the queue successfully : <span class="hljs-number">4</span>
delete a data from the queue successfully : <span class="hljs-number">5</span>
the size of queue : <span class="hljs-number">0</span>
traverse the queue : [<span class="hljs-number">0</span>, <span class="hljs-number">0</span>, <span class="hljs-number">0</span>, <span class="hljs-number">0</span>, <span class="hljs-number">0</span>, <span class="hljs-number">0</span>, <span class="hljs-number">0</span>, <span class="hljs-number">0</span>]</code></pre></div>


<h4 id="链表的实现方法"><a href="#链表的实现方法" class="headerlink" title="链表的实现方法"></a>链表的实现方法</h4><div class="hljs"><pre><code class="hljs java"><span class="hljs-keyword">package</span> pers.huangyuhui.queue;

<span class="hljs-comment">//定义一个单向链表</span>
<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">LLNode</span> </span>&#123;
    <span class="hljs-keyword">private</span> <span class="hljs-keyword">int</span> data;
    <span class="hljs-keyword">private</span> LLNode next;

    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">LLNode</span><span class="hljs-params">(<span class="hljs-keyword">int</span> data)</span> </span>&#123;
        <span class="hljs-keyword">this</span>.data = data;
    &#125;

    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">getData</span><span class="hljs-params">()</span> </span>&#123;
        <span class="hljs-keyword">return</span> data;
    &#125;

    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">setData</span><span class="hljs-params">(<span class="hljs-keyword">int</span> data)</span> </span>&#123;
        <span class="hljs-keyword">this</span>.data = data;
    &#125;

    <span class="hljs-function"><span class="hljs-keyword">public</span> LLNode <span class="hljs-title">getNext</span><span class="hljs-params">()</span> </span>&#123;
        <span class="hljs-keyword">return</span> next;
    &#125;

    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">setNext</span><span class="hljs-params">(LLNode next)</span> </span>&#123;
        <span class="hljs-keyword">this</span>.next = next;
    &#125;
&#125;


<span class="hljs-comment">/**
 * <span class="hljs-doctag">@project</span>: Data structures and algorithms
 * <span class="hljs-doctag">@description</span>: 基于链表实现队列
 * <span class="hljs-doctag">@author</span>: 黄宇辉
 * <span class="hljs-doctag">@date</span>: 9/1/2019-9:19 AM
 * <span class="hljs-doctag">@version</span>: 1.0
 * <span class="hljs-doctag">@website</span>: https://yubuntu0109.github.io/
 */</span>
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">LLQueue</span> </span>&#123;

    <span class="hljs-keyword">private</span> LLNode frontNode; <span class="hljs-comment">//represents headNode</span>
    <span class="hljs-keyword">private</span> LLNode rearNode; <span class="hljs-comment">//represents lastNode</span>

    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">LLQueue</span><span class="hljs-params">()</span> </span>&#123;
        <span class="hljs-keyword">this</span>.frontNode = <span class="hljs-keyword">null</span>;
        <span class="hljs-keyword">this</span>.rearNode = <span class="hljs-keyword">null</span>;
    &#125;

    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> LLQueue <span class="hljs-title">createQueue</span><span class="hljs-params">()</span> </span>&#123;
        <span class="hljs-keyword">return</span> <span class="hljs-keyword">new</span> LLQueue();
    &#125;

    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">isEmpty</span><span class="hljs-params">()</span> </span>&#123;
        <span class="hljs-keyword">return</span> (frontNode == <span class="hljs-keyword">null</span>);
    &#125;

    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">getQueueSize</span><span class="hljs-params">()</span> </span>&#123;
        <span class="hljs-keyword">int</span> length = <span class="hljs-number">0</span>;
        LLNode currentNode = frontNode;
        <span class="hljs-keyword">while</span> (currentNode != <span class="hljs-keyword">null</span>) &#123;
            length++;
            currentNode = currentNode.getNext();
        &#125;
        <span class="hljs-keyword">return</span> length;
    &#125;

    <span class="hljs-comment">//遍历</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">traverse</span><span class="hljs-params">()</span> </span>&#123;
        <span class="hljs-keyword">if</span> (isEmpty()) &#123;
            System.err.println(<span class="hljs-string">"error : the queue is empty !"</span>);
            <span class="hljs-keyword">return</span>;
        &#125;
        LLNode currentNode = frontNode;
        System.out.print(<span class="hljs-string">"the all data of queue : [ "</span>);
        <span class="hljs-keyword">while</span> (currentNode != <span class="hljs-keyword">null</span>) &#123;
            System.out.print(currentNode.getData() + <span class="hljs-string">" ,"</span>);
            currentNode = currentNode.getNext();
        &#125;
        System.out.print(<span class="hljs-string">" ]\n"</span>);
    &#125;

    <span class="hljs-comment">//入队</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">enQueue</span><span class="hljs-params">(<span class="hljs-keyword">int</span> data)</span> </span>&#123;
        LLNode newNode = <span class="hljs-keyword">new</span> LLNode(data);
        <span class="hljs-keyword">if</span> (rearNode != <span class="hljs-keyword">null</span>) &#123;
            rearNode.setNext(newNode);
        &#125;
        rearNode = newNode;
        <span class="hljs-keyword">if</span> (frontNode == <span class="hljs-keyword">null</span>) &#123;
            frontNode = rearNode;
        &#125;
        System.out.println(<span class="hljs-string">"enter the data into the queue successfully : "</span> + data);
    &#125;

    <span class="hljs-comment">//出队</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">deQueue</span><span class="hljs-params">()</span> </span>&#123;
        <span class="hljs-keyword">int</span> data = <span class="hljs-number">0</span>;
        <span class="hljs-keyword">if</span> (isEmpty()) &#123;
            System.err.println(<span class="hljs-string">"error : the queue is empty"</span>);
        &#125; <span class="hljs-keyword">else</span> &#123;
            data = frontNode.getData();
            frontNode = frontNode.getNext();
        &#125;
        System.out.println(<span class="hljs-string">"delete the data from the queue successfully : "</span> + data);
        <span class="hljs-keyword">return</span> data;
    &#125;


    <span class="hljs-comment">//test</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> </span>&#123;
        LLQueue queue = LLQueue.createQueue();
        <span class="hljs-comment">//enter</span>
        queue.enQueue(<span class="hljs-number">1</span>);
        queue.enQueue(<span class="hljs-number">2</span>);
        queue.enQueue(<span class="hljs-number">3</span>);
        queue.enQueue(<span class="hljs-number">4</span>);
        queue.enQueue(<span class="hljs-number">5</span>);
        System.out.println(<span class="hljs-string">"the size of the queue : "</span> + queue.getQueueSize());
        System.out.print(<span class="hljs-string">"traverse the queue : "</span>);
        queue.traverse();
        <span class="hljs-comment">//delete</span>
        queue.deQueue();
        queue.deQueue();
        queue.deQueue();
        queue.deQueue();
        queue.deQueue();
        System.out.println(<span class="hljs-string">"the size of the queue : "</span> + queue.getQueueSize());
        System.out.print(<span class="hljs-string">"traverse the queue : "</span>);
        queue.traverse();

    &#125;

&#125;</code></pre></div>

<p><em>程序运行结果如下所示 :</em></p>
<div class="hljs"><pre><code class="hljs java">enter the data into the queue successfully : <span class="hljs-number">1</span>
enter the data into the queue successfully : <span class="hljs-number">2</span>
enter the data into the queue successfully : <span class="hljs-number">3</span>
enter the data into the queue successfully : <span class="hljs-number">4</span>
enter the data into the queue successfully : <span class="hljs-number">5</span>
the size of the queue : <span class="hljs-number">5</span>
traverse the queue : the all data of queue : [ <span class="hljs-number">1</span> ,<span class="hljs-number">2</span> ,<span class="hljs-number">3</span> ,<span class="hljs-number">4</span> ,<span class="hljs-number">5</span> , ]

delete the data from the queue successfully : <span class="hljs-number">1</span>
delete the data from the queue successfully : <span class="hljs-number">2</span>
delete the data from the queue successfully : <span class="hljs-number">3</span>
delete the data from the queue successfully : <span class="hljs-number">4</span>
delete the data from the queue successfully : <span class="hljs-number">5</span>
the size of the queue : <span class="hljs-number">0</span>
traverse the queue : error : the queue is empty !</code></pre></div>



<p><em>参考书籍( 已纠正书中错误的示例代码 ) : 《数据结构与算法经典问题解析 - 原书第2版》</em></p>

            </article>
            <hr>
            <div>
              <div class="post-metas mb-3">
                
                
                  <div class="post-meta">
                    <i class="iconfont icon-tags"></i>
                    
                      <a class="hover-with-bg" href="/tags/Java/">Java</a>
                    
                      <a class="hover-with-bg" href="/tags/Data-Structures-and-Algorithms/">Data Structures and Algorithms</a>
                    
                  </div>
                
              </div>
              
                <p class="note note-warning">本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-sa/4.0/deed.zh" target="_blank" rel="nofollow noopener noopener">CC BY-SA 4.0 协议</a> ，转载请注明出处！</p>
              
              
                <div class="post-prevnext row">
                  <div class="post-prev col-6">
                    
                    
                      <a href="/2019/09/01/%E8%AF%A6%E8%A7%A3Binary-Tree%E7%9A%84%E5%AE%9E%E7%8E%B0%E6%96%B9%E5%BC%8F%E5%8F%8A%E5%85%B6%E5%BA%94%E7%94%A8/">
                        <i class="iconfont icon-arrowleft"></i>
                        <span class="hidden-mobile">详解Binary Tree的实现方式及其应用</span>
                        <span class="visible-mobile">Previous</span>
                      </a>
                    
                  </div>
                  <div class="post-next col-6">
                    
                    
                      <a href="/2019/08/31/%E8%BD%AF%E4%BB%B6%E5%B7%A5%E7%A8%8B%E7%90%90%E7%A2%8E%E7%9F%A5%E8%AF%86%E7%82%B9/">
                        <span class="hidden-mobile">软件工程琐碎知识点</span>
                        <span class="visible-mobile">Next</span>
                        <i class="iconfont icon-arrowright"></i>
                      </a>
                    
                  </div>
                </div>
              
            </div>

            
          </div>
        </div>
      </div>
    </div>
    
      <div class="d-none d-lg-block col-lg-2 toc-container" id="toc-ctn">
        <div id="toc">
  <p class="toc-header"><i class="iconfont icon-list"></i>&nbsp;TOC</p>
  <div id="tocbot"></div>
</div>

      </div>
    
  </div>
</div>

<!-- Custom -->


    
  </main>

  
    <a id="scroll-top-button" href="#" role="button">
      <i class="iconfont icon-arrowup" aria-hidden="true"></i>
    </a>
  

  
    <div class="modal fade" id="modalSearch" tabindex="-1" role="dialog" aria-labelledby="ModalLabel"
     aria-hidden="true">
  <div class="modal-dialog modal-dialog-scrollable modal-lg" role="document">
    <div class="modal-content">
      <div class="modal-header text-center">
        <h4 class="modal-title w-100 font-weight-bold">Search</h4>
        <button type="button" id="local-search-close" class="close" data-dismiss="modal" aria-label="Close">
          <span aria-hidden="true">&times;</span>
        </button>
      </div>
      <div class="modal-body mx-3">
        <div class="md-form mb-5">
          <input type="text" id="local-search-input" class="form-control validate">
          <label data-error="x" data-success="v"
                 for="local-search-input">keyword</label>
        </div>
        <div class="list-group" id="local-search-result"></div>
      </div>
    </div>
  </div>
</div>
  

  

  

  <footer class="mt-5">
  <div class="text-center py-3">
    <div>
      <a href="https://hexo.io" target="_blank" rel="nofollow noopener"><span>Hexo</span></a>
      <i class="iconfont icon-love"></i>
      <a href="https://github.com/fluid-dev/hexo-theme-fluid" target="_blank" rel="nofollow noopener">
        <span>Fluid</span></a>
    </div>
    
  <div class="statistics">
    
    

    
      
        <!-- 不蒜子统计PV -->
        <span id="busuanzi_container_site_pv" style="display: none">
            总访问量 
            <span id="busuanzi_value_site_pv"></span>
             次
          </span>
      
      
        <!-- 不蒜子统计UV -->
        <span id="busuanzi_container_site_uv" style="display: none">
            总访客数 
            <span id="busuanzi_value_site_uv"></span>
             人
          </span>
      
    
  </div>


    

    
  </div>
</footer>

<!-- SCRIPTS -->
<script  src="https://cdn.staticfile.org/jquery/3.4.1/jquery.min.js" ></script>
<script  src="https://cdn.staticfile.org/twitter-bootstrap/4.4.1/js/bootstrap.min.js" ></script>
<script  src="/js/debouncer.js" ></script>
<script  src="/js/main.js" ></script>

<!-- Plugins -->


  
    <script  src="/js/lazyload.js" ></script>
  



  <script defer src="https://cdn.staticfile.org/clipboard.js/2.0.6/clipboard.min.js" ></script>
  <script  src="/js/clipboard-use.js" ></script>



  <script defer src="https://busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js" ></script>





  <script  src="https://cdn.staticfile.org/tocbot/4.11.1/tocbot.min.js" ></script>
  <script>
    $(document).ready(function () {
      var boardCtn = $('#board-ctn');
      var boardTop = boardCtn.offset().top;

      tocbot.init({
        tocSelector: '#tocbot',
        contentSelector: 'article.markdown-body',
        headingSelector: 'h1,h2,h3,h4,h5,h6',
        linkClass: 'tocbot-link',
        activeLinkClass: 'tocbot-active-link',
        listClass: 'tocbot-list',
        isCollapsedClass: 'tocbot-is-collapsed',
        collapsibleClass: 'tocbot-is-collapsible',
        collapseDepth: 0,
        scrollSmooth: true,
        headingsOffset: -boardTop
      });
      if ($('.toc-list-item').length > 0) {
        $('#toc').css('visibility', 'visible');
      }
    });
  </script>



  <script  src="https://cdn.staticfile.org/typed.js/2.0.11/typed.min.js" ></script>
  <script>
    var typed = new Typed('#subtitle', {
      strings: [
        '  ',
        "详解Queue的实现方式及其应用&nbsp;",
      ],
      cursorChar: "_",
      typeSpeed: 70,
      loop: false,
    });
    typed.stop();
    $(document).ready(function () {
      $(".typed-cursor").addClass("h2");
      typed.start();
    });
  </script>



  <script  src="https://cdn.staticfile.org/anchor-js/4.2.2/anchor.min.js" ></script>
  <script>
    anchors.options = {
      placement: "right",
      visible: "hover",
      
    };
    var el = "h1,h2,h3,h4,h5,h6".split(",");
    var res = [];
    for (item of el) {
      res.push(".markdown-body > " + item)
    }
    anchors.add(res.join(", "))
  </script>



  <script  src="/js/local-search.js" ></script>
  <script>
    var path = "/local-search.xml";
    var inputArea = document.querySelector("#local-search-input");
    inputArea.onclick = function () {
      searchFunc(path, 'local-search-input', 'local-search-result');
      this.onclick = null
    }
  </script>



  <script  src="https://cdn.staticfile.org/fancybox/3.5.7/jquery.fancybox.min.js" ></script>
  <link  rel="stylesheet" href="https://cdn.staticfile.org/fancybox/3.5.7/jquery.fancybox.min.css" />

  <script>
    $('#post img:not(.no-zoom img, img[no-zoom]), img[zoom]').each(
      function () {
        var element = document.createElement('a');
        $(element).attr('data-fancybox', 'images');
        $(element).attr('href', $(this).attr('src'));
        $(this).wrap(element);
      }
    );
  </script>







  
  
    <script>
      !function (e, t, a) {
        function r() {
          for (var e = 0; e < s.length; e++) s[e].alpha <= 0 ? (t.body.removeChild(s[e].el), s.splice(e, 1)) : (s[e].y--, s[e].scale += .004, s[e].alpha -= .013, s[e].el.style.cssText = "left:" + s[e].x + "px;top:" + s[e].y + "px;opacity:" + s[e].alpha + ";transform:scale(" + s[e].scale + "," + s[e].scale + ") rotate(45deg);background:" + s[e].color + ";z-index:99999");
          requestAnimationFrame(r)
        }

        function n() {
          var t = "function" == typeof e.onclick && e.onclick;
          e.onclick = function (e) {
            t && t(), o(e)
          }
        }

        function o(e) {
          var a = t.createElement("div");
          a.className = "heart", s.push({
            el: a,
            x: e.clientX - 5,
            y: e.clientY - 5,
            scale: 1,
            alpha: 1,
            color: c()
          }), t.body.appendChild(a)
        }

        function i(e) {
          var a = t.createElement("style");
          a.type = "text/css";
          try {
            a.appendChild(t.createTextNode(e))
          } catch (t) {
            a.styleSheet.cssText = e
          }
          t.getElementsByTagName("head")[0].appendChild(a)
        }

        function c() {
          return "rgb(" + ~~(255 * Math.random()) + "," + ~~(255 * Math.random()) + "," + ~~(255 * Math.random()) + ")"
        }

        var s = [];
        e.requestAnimationFrame = e.requestAnimationFrame || e.webkitRequestAnimationFrame || e.mozRequestAnimationFrame || e.oRequestAnimationFrame || e.msRequestAnimationFrame || function (e) {
          setTimeout(e, 1e3 / 60)
        }, i(".heart{width: 10px;height: 10px;position: fixed;background: #f00;transform: rotate(45deg);-webkit-transform: rotate(45deg);-moz-transform: rotate(45deg);}.heart:after,.heart:before{content: '';width: inherit;height: inherit;background: inherit;border-radius: 50%;-webkit-border-radius: 50%;-moz-border-radius: 50%;position: fixed;}.heart:after{top: -5px;}.heart:before{left: -5px;}"), n(), r()
      }(window, document);
    </script>
  














</body>
</html>
